package C057;

import java.util.HashMap;

/**
 * ClassName: c01
 * Package: C057
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/4/27 21:45
 * @Version 1.0
 * @Since 1.0
 */
public class c01 {
    public static void main(String[] args) {
        int[][] arr = {{0,0},{0,2},{1,1},{2,0},{2,2}};
        System.out.println(removeStones(arr));
    }

    static HashMap<Integer, Integer> rowMap = new HashMap<>();
    static HashMap<Integer, Integer> colMap = new HashMap<>();
    static int MAXLEN = 10000;
    static int[] father = new int[MAXLEN];
    static int[] stack = new int[MAXLEN];
    static int sets, n, row, col, size;
    public static int removeStones(int[][] stones) {
        n = stones.length;
        build();
        for (int i = 0; i < stones.length; i++) {
            row = stones[i][0];
            col = stones[i][1];
            // 行数据
            if(rowMap.containsKey(row)) {
                // 合并
                union(rowMap.get(row), i);
            } else {
                rowMap.put(row, i);
            }

            // 列数据
            if(colMap.containsKey(col)) {
                // 合并
                union(colMap.get(col), i);
            } else {
                colMap.put(col, i);
            }
        }
        return n - sets;
    }

    private static void union(Integer i, Integer j) {
        int fatheri = find(i);
        int fatherj = find(j);
        if(fatheri == fatherj) {
            return;
        }
        father[fatherj] = fatheri;
        sets --;
    }


    private static int find(Integer i) {
        size = 0;
        while(i != father[i]) {
            stack[size ++] = i;
            i = father[i];
        }
        while(size > 0) {
            father[stack[-- size]] = i;
        }
        return i;
    }

    private static void build() {
        rowMap.clear();
        colMap.clear();
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
        sets = n;
    }
}
